<?php
// leetcode 144题二叉树的后序遍历
class TreeNode {
    protected $val = null;
    protected $left = null;
    protected $right = null;

    public function __construct($val = 0, $left = null, $right = null)
    {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}
class Solution {
    function postorderTraversal($root) {
        if ($root == null) return [];
        // 遍历左子树
        $left = $this->postorderTraversal($root->left);
        // 遍历右子树
        $right = $this->postorderTraversal($root->right);
        // 节点值添加到数组
        $arr[] = $root->val;
        return array_merge($left, $right, $arr);
    }

    // 从上到下，从左至右依次压入栈中
    function postorderTraversal2($root) {
        $stack = new SplStack();
        $res = [];
        if ($root === null) return $res;
        $stack->push($root);
        while ($stack->count()) {
            $cur = $stack->pop();
            array_unshift($res, $cur->val);
            if ($cur->left != null) $stack->push($cur->left);
            if ($cur->right != null) $stack->push($cur->right);
        }
        return $res;
    }
}
